import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;


public class Sort {


    /*
    *  直接插入排序 ---- 稳定的
    *  时间复杂度 ： 最坏情况下：O（N^2）
    *  适用于： 待排序序列已经基本趋于有序的情况
    *  空间复杂度：O（1）
    * */
    public static void insertSort(int[] array){
        for(int i=1;i<array.length;i++) {
            int j = i - 1;
            int tmp = array[i];
            for (; j >= 0; j--) {
                // 用来记录 插入的值
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }


    /*
    *  希尔排序---- 不稳定的
    *  缩小增量
    *  分成多组进行直接排序
    *  分组越到后面 排序效率越快
    * */

    public static void shellSort(int[] array){
        int k=array.length;
        while(k>=1){
            // 此处是分为k组，每组进行直接插入排序
            k/=2;
            shell(array,k);
        }
    }
    private static void shell(int[] array,int k){
        for(int i=k;i<array.length;i++) {
            int j = i - k;
            int tmp = array[i];
            // 对每组进行排序，每组间元素下标相差k
            for (; j >= 0; j-=k) {
                // 用来记录 插入的值
                if (array[j] > tmp) {
                    array[j + k] = array[j];
                } else {
                    break;
                }
            }
            array[j + k] = tmp;
        }
    }



    /* 选择排序 ---- 不稳定的
    *  时间复杂度 ： 最坏情况下：O（N^2）
    *  空间复杂度：O（1）
    * */
    public static void selectSort(int[] array){
        for(int i=0;i<array.length;i++){
            // 用来记录最小值的下标， 每循环一次找到最小值
            int minIndex=i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    // 双向选择排序
    public static void selectSort2(int[] array){
            // 用来记录最左边最右边的值下标
            int left=0;
            int right=array.length-1;
            while (left<right) {
                // 记录最大最小值下标
                int minIndex=left;
                int maxIndex=left;
                for (int i = left+1; i <=right; i++) {
                    if (array[i] > array[maxIndex]) {
                        maxIndex = i;
                    }
                    if (array[i] < array[minIndex]) {
                        minIndex = i;
                    }
                }
                swap(array,left,minIndex);
                // 如果要交换的最大值正好是left，那么经过上面的交换，max就交换走了
                if(maxIndex==left){
                    maxIndex=minIndex;
                }
                swap(array,right,maxIndex);
                left++;
                right--;
            }
    }

    private  static void swap(int[] array,int i,int minIndex){
        int tmp=array[i];
        array[i]=array[minIndex];
        array[minIndex]=tmp;
    }




    /*  堆排序
        时间复杂度：O（N*logN）
        不稳定的
    */

    public static void heapSort(int[] array){
        // 首先创建一个大根堆
        creatHeap(array);
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    private static void creatHeap(int[] array){
        for(int parent=(array.length-2)/2;parent>=0;parent--){
            siftDown(array,parent,array.length);
        }
    }
    private static void siftDown(int[] array,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if(child+1<len && array[child] < array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }



    /*
    *   冒泡排序
    *   时间复杂度：O（N^2）
    *   稳定的
    * */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                }
            }
        }
    }



    /*
    *  快速排序
    *  时间复杂度：O(N*logN)
    *  稳定的
    * */


    // Hoare法
    public static void quickSort(int[] array){
        quick(array,0, array.length-1);
    }
    // middle方法用来求基准值
    private static int middle(int[] array,int left,int right){
        int mid=(left+right)/2;
        if(array[left] > array[right]){
            if(array[mid] < array[right]){
                return right;
            }else if(array[mid] > array[left]){
                return  left;
            }else{
                return mid;
            }
        }else{
            // array[left] < array[right]
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return  right;
            }else{
                return mid;
            }
        }
    }
    private static void quick(int[] array,int begin,int end){
        if(begin>=end){
            return ;
        }
        //快速排序的优化： 保证了尽量基准值两边的值一样多
        int mid=middle(array,begin,end);
        swap(array,mid,begin);     // 将基准中间值 换到第一位

        // 用来记录基准值所存放的下标
        int partition=partitionHoare(array,begin,end);
        quick(array,begin,partition-1);
        quick(array,partition+1,end);
    }
    private static int partitionHoare(int[] array,int left,int right){
        int i=left;
        int tmp=array[left];
        while(left<right){
            // 先找到比基准值小的值的下标
            while(array[right] >= tmp && left<right){
                right--;
            }
            while (array[left] <= tmp && left<right){
                left++;
            }

            swap(array,left,right);
        }
        swap(array,i,left);
        return left;
    }


    // 挖坑法
    private static int partition(int[] array,int left,int right){
        int i=left;
        // 将基准值所在位置空出来
        int tmp=array[left];
        while(left<right){
            // 从后面找到比基准值小的数
            while(array[right] >= tmp && left<right){
                right--;
            }
            // 将小的数交换到前面来
            array[right]= array[left];
            // 在从前面找到比基准值大的值
            while (array[left] <= tmp && left<right){
                left++;
            }
            // 将后面交换到前面的值的空补起来
            array[left]=array[right];

        }
        array[left]=tmp;
        return left;
    }

    // 非递归的快速排序
    public static void quickSortNor(int[] array){
        int left= 0;
        int right = array.length-1;
        // 定义一个栈用来存储区间下标
        Stack<Integer> st = new Stack<>();
        int div = partitionHoare(array, left, right);
        if(div-1 > left){
            st.push(left);
            st.push(div);
        }
        // 说明右边就一个
        if(div+1 < right){
            st.push(div+1);
            st.push(right);
        }

        while (!st.empty()) {
            // 取出栈中元素 作为区间
            right = st.pop();
            left = st.pop();
            div = partitionHoare(array, left, right);
            if(div-1 > left){
                st.push(left);
                st.push(div);
            }
            // 说明右边就一个
            if(div+1 < right){
                st.push(div+1);
                st.push(right);
            }


        }
    }


    /*
    *  归并排序
    * */
    public static void mergeSort(int[] array){
        mergeSort(array,0, array.length-1);
    }
    private static void mergeSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        // 分解
        int mid =(left+right)/2;
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);

        // 合并
        merge(array,left,mid,right);
    }
    private static void merge(int[] array,int left,int mid,int right){
        // 定义一个数组用来存储
        int[] tmp=new int[right-left+1];
        int k=0;

        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;

        while (s1<=e1 && s2<=e2){
            if(array[s1] <array[s2]){
                tmp[k++] =array[s1++];
            }else{
                tmp[k++] =array[s2++];
            }
        }
        while(s1<=e1){
            tmp[k++] =array[s1++];
        }
        while(s2<=e2){
            tmp[k++] =array[s2++];
        }

        for(int i=0;i< tmp.length;i++){
            array[left+i]=tmp[i];
        }
    }


    // 非递归实现
    public static void mergeSortNor(int[] array){
        // 用来记录每组的个数
        int gap=1;
        while (gap< array.length) {
            for (int i = 0; i < array.length; i += gap*2) {
                int left = i;
                int mid = left + gap-1;
                int right = gap + mid;
                // 判断是否越界
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                if (right >= array.length) {
                    right = array.length - 1;
                }
                // 用来排序
                merge(array, left, mid, right);
            }
            gap *= 2;
        }
    }






    /*
    *  计数排序
    * */
    public static void countSort(int[] array){
        int minValue=array[0];
        int maxValue=array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i] < minValue){
                minValue=array[i];
            }
            if(array[i] > maxValue){
                maxValue=array[i];
            }
        }
        int len=maxValue-minValue+1;
        int[] tmp=new int[len];
        for(int i=0;i< array.length;i++){
            tmp[array[i]-minValue]++;
        }
        int index=0;
        for (int i = 0; i < len; i++){
            while (tmp[i]>0){
                array[index++]=i+minValue;
                tmp[i]--;
            }
        }

    }
}
